package bTree.LeetCode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class 按对角线进行矩阵排序 {
    public int[][] sortMatrix(int[][] grid) {
        int n = grid.length;
        //左下半部分
        int cnt = 0;
        for (int i = n - 1; i >= 0; i--) {
            List<Integer> path = new ArrayList<>();
            for (int j = 0; j <= cnt; j++) {
                path.add(grid[i + j][j]);
            }
            Collections.sort(path);
            Collections.reverse(path);
            for (int j = 0; j <= cnt; j++) {
                grid[i + j][j] = path.get(j);
            }
            cnt++;
        }

        //右上半部分
        cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            List<Integer> path = new ArrayList<>();
            for (int j =0; j <=cnt; j++) {
                path.add(grid[i -j][n-1-j]);
            }
            Collections.sort(path);
            Collections.reverse(path);
            for (int j = 0; j <= cnt; j++) {
                grid[i -cnt][n-1-j] = path.get(j);
            }
            cnt++;
        }
        return grid;
    }
}